package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  数字字符转化问题 <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/17 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 数字字符转化问题 {
    /**
     *    1、规定1和A对应，2和B对应，3和C对应...。那么一个数字字符比如"111"就可以转化为："AAA","KA","AK"。
     *
     *     给定一个只有数字字符组成的字符串str,返回有多少种转化结果
      */
    public static void main(String[] args) {
        System.out.println(number("111"));
        System.out.println(number1("111"));
        System.out.println(number2("111"));
    }
    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        List<String> ans = new ArrayList<>();
        char[] chars = str.toCharArray();
        String path = "";
        // i初始为0，表示0位置往后有多少中转化结果
        int res= numtoString(chars, 0,ans,path);
        System.out.println(ans);
        return res;
    }
//    todo 这么写是想记录 每种情况可能出现的字母，但失败了，失败了是因为参数是数字，不是字母
    public static int numtoString(char[] str, int index , List<String> ans, String path){
        if (index==str.length){
            ans.add(path);
            return 1;  // 此时字符串算一种情况
        }
        if (str[index]=='0'){
            return 0;
        }
        if (str[index]=='1'){
            String less = path;
           int res = numtoString(str,index+1,ans,less); // 情况1 逐个元素转化
            if (index+1<str.length){
                String more = path+ str[index+1];
               res+= numtoString(str,index+2,ans,more); // 情况2 能与后一个元素一起转化。11--19

            }
            return res;
        }
        if (str[index]=='2'){
            String less = path;
            int res = numtoString(str,index+1,ans,less); // 情况1 逐个元素转化
            if (index+1<str.length &&(str[index+1] >='0' && str[index+1]<='6')){
                // 情况2 能与后一个元素一起转化。20--26
                String more = path+ str[index+1];
                res+= numtoString(str,index+2,ans,more);
            }
            return res;
        }
        //其余字符无法一起转化：需要逐个转化：
       return numtoString(str,index+1,ans,path);

    }

    public static int number1(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        // i初始为0，表示0位置往后有多少中转化结果
        return process(str.toCharArray(), 0);
    }

    // str[0...i-1]已经转化完了，固定了
    // i之前的位置，如何转化已经做过决定了, 不用再关心
    // i... 有多少种转化的结果
    public static int process(char[] str, int i) {
        // i和字符串长度一样大，右侧没有字符了。找到1中转化是0~n-1位置的转化
        if (i == str.length) { // base case
            return 1;
        }
        // i之前的决策，让当前i位置单独面对一个0字符，那么之前决策错误，返回0
        // 例如10先转化为A，2位置是0字符无法转化，当前决策无效
        // 而10直接转化为J,直接到终止位置，返回一种转化J
        if (str[i] == '0') {
            return 0;
        }

        // i位置如果是1或者2，有可能和下一个位置共同转化，因为字符数为0~26
        // 反之3~9超过26不需要决策

        // str[i] 如果是1，总是有两个选择，因为最大为19，不超过26
        if (str[i] == '1') {
            int res = process(str, i + 1);
            if (i + 1 < str.length) {
                res += process(str, i + 2);
            }
            return res;
        }
        // str[i] 如果是2，那么有可能有两种选择，需要看是否朝贡国26
        if (str[i] == '2') {
            int res = process(str, i + 1);
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                res += process(str, i + 2); // (i和i+1)作为单独的部分，后续有多少种方法
            }
            return res;
        }
        // str[i] 在3~9的位置，下个位置必须决策一种选择
        return process(str, i + 1);
    }

    public static int number2(String str){
        if (str==null||str.length()<=0){
            return 0;
        }
        return  process1(str.toCharArray(),0);
    }

    static int process1( char[] s ,int i){
        // 此时为最后一个字母
        int n = s.length;
        if (i==n){
            return  1;
        }
        // 0
        if (s[i]=='0'){
            return 0;
        }
        // 1
        if (s[i]=='1'){
            int count = process1(s,i+1);
            if (i+1<n){
                // 因为i从0开始，故<n,不是<=n
                count+=process1(s,i+2);
            }
            return count;
        }
        if (s[i]=='2'){
            int count = process1(s, i+1);
            if (i+1<n&&(s[i+1]>='0'&&s[i+1]<='6')){
                count+=process1(s,i+2);
            }
            return count;

        }

        int count=process1(s,i+1);
        return count;
    }

}
